package Array_and_String;
/*
实现 strStr()
给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
如果needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/cm5e2/
 */

public class _34实现strStr {
    public static void main(String[] args) {
        String haystack = "mississippi";
        String needle = "issipi";

        System.out.println(strStr(haystack, needle));

    }

    //方法一:暴力枚举
    public static int strStr(String haystack, String needle) {
        if(needle.length() > haystack.length()){
            return -1;
        }

        for (int i = 0; i < haystack.length(); i++) {
            boolean b = true;
            for (int j = 0; j < needle.length(); j++) {
                if(i + j >= haystack.length()){
                    return -1;
                }
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    b = false;
                    break;
                }
            }
            if (b) {
                return i;
            }

        }
        return -1;


    }

    //方法二:KMP解法
    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr2(String ss, String pp) {
        if (pp.isEmpty()) return -1;

        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        //最长公共前后缀
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            //正常情况j一直在左侧徘徊   i则相当于子串最右侧的索引  j在徘徊的时候已经应用了KMP解法
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1])
                j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1])
                j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }


        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }

        return -1;
    }



    public int strStr3(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();

        if (needle.isEmpty() || n < m) return -1;

        haystack = " " + haystack;
        needle = " " + needle;

        int[] next = new int[m + 1];
        //构造next数组
        for (int i = 2 , j = 0; i <= m; i++){
            //如果不成功
            while (j > 0 && needle.charAt(i) != needle.charAt(j + 1)){
                j = next[j];
            }

            //如果成功
            if (needle.charAt(i) == needle.charAt(j + 1)) {
                j++;
            }

            next[i] = j;

        }

        //开始KMP匹配
        for(int i = 1,j = 0; i <= n; i++){
            //如果不成功
            while (j > 0 && haystack.charAt(i) != needle.charAt(j + 1)){
                j = next[j];
            }
            //如果成功
            if (haystack.charAt(i) == needle.charAt(j + 1)) {
                j++;
            }

            if (j == m) return i - m;

        }

        return -1;

    }
}
